---
title: "迷宫"
created: 2025-11-28
tags:
  - 算法
---

# 迷宫

## 题目 [迷宫](https://www.luogu.com.cn/problem/P1605)

![[image-c0c38d06.png]]

## 思路分析

路径数用dfs

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=10;

int g[N][N];

int st[N][N];

int n,m,T;

int sx,sy,fx,fy;

int cnt;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=n && !st[x][y];

}

void dfs(int x,int y){

	if(x==fx && y==fy){

		cnt++;

		return;

	}

	for(int i=0;i<4;i++){

		int nx=x+dx[i],ny=y+dy[i];

		if(isVaild(nx,ny) && g[nx][ny]==0){

			st[nx][ny]=true;

			dfs(nx,ny);

			st[nx][ny]=false;

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m>>T;

	cin>>sx>>sy>>fx>>fy;

	while(T--){

		int tempx,tempy;

		cin>>tempx>>tempy;

		g[tempx][tempy]=1;

	}

	st[sx][sy]=true;

	dfs(sx,sy);

	cout<<cnt;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[简单图|简单图]] 🏠 [[00-刷题理模型]] ➡️ [[数的划分|数的划分]]